字符串解码

题目描述：给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”

示例 3：
输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”

示例 4：
输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”

栈

• 外层的解码需要等待内层解码的结果。先扫描的字符还用不上，但不能忘了它们。
• 我们准备由内到外，层层解决[ ]，需要保持对字符的记忆，于是用栈。

入栈和出栈的时机

• 入栈时机：遇到[。意味着要解决内部的人了，外部的数字和字母，去栈里等。

  • 当遇到[，已经扫描的数字就是“倍数”，入栈暂存

  • 当遇到[，已经扫描的字母也入栈等待，括号里的解码完了，一起参与构建字符串。

    

• 出栈时机：遇到]。内层的扫描完了，栈顶元素可以出栈了，共同参与子串的构建。

  • 栈顶就是最近遇到的“倍数”和字母

var decodeString = function (s) {
  let numStack = [], strStack = []  // 存倍数、待拼接 str 的栈
  let num = 0, res = ''  // 倍数、字符串的“搬运工”
  for(const char of s) { // 逐字符扫描
    if(!isNaN(char)) { // 遇到数字
      num = num * 10 + Number(char) // 算出倍数
    } else if(char === '[') { // 遇到 [
      numStack.push(num)  // 倍数num进入栈等待
      num = 0  // 入栈后清零
      strStack.push(res) // result串入栈
      res = '' // 入栈后清零
    } else if(char === ']') { // 遇到 ]，两个栈的栈顶出栈
      let num = numStack.pop() // 获取拷贝次数
      res = strStack.pop() + res.repeat(num) // 构建子串
    } else {
      res += char // 遇到字母，追加给result串
    }
  }
  return res
};

console.log(decodeString('3[a2[c]]'))

复杂度分析

• 时间复杂度：O(N)。N 是解码后字符串的长度

• 空间复杂度：O(N)。

正则

var decodeString = function (s) {
  let reg = /(\d+)\[([a-zA-Z]+)\]/g;
  while (s.indexOf('[') > 0) {
    s = s.replace(reg, (_, ...[num, str]) => {
      return str.repeat(Number(num))
    });
  }
  return s;
};

console.log(decodeString('3[a2[c]]'))